1. Field of the Invention
The present invention relates generally to the field of parallel processing and, more specifically, to a system and method for optimizing the evaluation of task dependency graphs.
2. Description of the Related Art
A parallel computation environment allows different tasks related to the same program to be executed in parallel. To make use of a parallel computation environment, a compiler decomposes a program into fine-grained tasks that are represented by a task dependency graph. The task dependency graph indicates the dependency between each pair of tasks and the order in which tasks are to be executed.
During the execution of the tasks in the parallel computation environment, each fine-grained task can be executed on a different processing engine within the parallel computation environment. To ensure the proper execution of the program, the execution order and the dependencies between tasks are managed via the task dependency graph and sophisticated task scheduling policies. However, even with optimized task scheduling policies, fine grained tasks result in a large amount of overhead on the parallel computation environment.
More specifically, each processing engine within the parallel computation environment needs to communicate with every other processing engine to indicate the completion of different tasks. Requiring inter-engine communication increases the processing burden on the processing engine as state needs to be managed and tracked constantly. In addition, tasks that are not dependent on any outstanding tasks but are not at the top of the input queue are not processed even when there is processing bandwidth, thus unnecessarily slowing down the processing of work.
As the foregoing illustrates, what is needed in the art is a mechanism for optimizing the evaluation of tasks specified by a task dependency graph.